package main

import (
	"cmp"
	"fmt"
	"math/rand"
)

// 描述：从前往后的每个元素，依次往前按比较结果插入
func InsertSort[T cmp.Ordered](s []T) []T {
	if s == nil {
		return nil
	}
	for i := 1; i < len(s); i++ {
		for j := 0; j < i; j++ {
			if s[i] < s[j] {
				s[i], s[j] = s[j], s[i]
			}
		}
	}
	return s
}

func InsertSortComparator[T cmp.Ordered](s []T, comparator func(a T, b T) int) []T {
	if s == nil {
		return nil
	}
	for i := 1; i < len(s); i++ {
		for j := 0; j < i; j++ {
			if comparator(s[i], s[j]) < 0 {
				s[i], s[j] = s[j], s[i]
			}
		}
	}
	return s
}

func InsertSortTest() {
	fmt.Println("------------InsertSortTest------------")
	s := []int{1, 2, 3, 4, 5, 6, 7}
	rand.Shuffle(len(s), func(i, j int) {
		s[i], s[j] = s[j], s[i]
	})
	fmt.Println("pre", s)
	s = InsertSort(s)
	fmt.Println("cur", s)

	rand.Shuffle(len(s), func(i, j int) {
		s[i], s[j] = s[j], s[i]
	})
	fmt.Println("pre", s)
	s = InsertSortComparator(s, func(a int, b int) int {
		// 返回-1， a就在前
		if a > b {
			return -1
		} else {
			return 1
		}
	})
	fmt.Println("cur", s)
	fmt.Println("------------InsertSortTest------------")
}
